package tree;

public class BinarySearchTree {
    /**
     * Node for Binary Search Tree
     */
    class Node {
        private Node p; /// parent node
        private Node left; /// left child
        private Node right; /// right child
        private int key; /// key value
    }

    /**
     * search key = k in the tree, which root node is x, using iteration
     * @param x current node, used as root node
     * @param k key value, used as searching object
     * @return search result
     * - null there is no node with key = k
     * - not null, the node with key = k
     */
    public Node treeSearch(Node x, int k) {
        if (null == x || x.key == k) return x;

        if (k < x.key) return treeSearch(x.left, k);
        else return treeSearch(x.right, k);
    }

    /**
     * search key = k in the tree, which root node is x, using loop
     * @param x current node, used as root node
     * @param k key value, used as searching object
     * @return search result
     * - null there is no node with key = k
     * - not null, the node with key = k
     */
    public Node treeSearch_2(Node x, int k) {
        if (null == x || x.key == k) return x;

        while (null != x && x.key != k) {
            if (k < x.key) x = x.left;
            else x = x.right;
        }
        return x;
    }
}
